#include<bits/stdc++.h>

using namespace std;
using ll = long long;
#define endl '\n'
//sort a[left..right]
//T(n)=2*T(n/2)+O(n)=>T(n)=O(nlogn)
int buf[100000];

void merge_sort(int *a, int left, int right) {
    if (left >= right)return;
    int mid = (left + right) / 2;
    //a[left,mid] a[mid+1,right]
    merge_sort(a, left, mid);
    merge_sort(a, mid + 1, right);

    //merge
    int i = left, j = mid + 1, k = left;
    while (i <= mid && j <= right) {
        if (a[i] <= a[j]) {
            buf[k++] = a[i++];
        } else {
            buf[k++] = a[j++];
        }
    }
    while (i <= mid) {
        buf[k++] = a[i++];
    }
    while (j <= right) {
        buf[k++] = a[j++];
    }
    for (int k = left; k <= right; k++) {
        a[k] = buf[k];
    }
}

int main() {
    int a[] = {1, 3, 5, 7, 9, 2, 4, 6, 8, 0};
    merge_sort(a, 0, 9);//a[0..9]
    //stable_sort(a,a+10);//STL stable sort 就是merge_sort
    for (int i = 0; i < 10; i++) {
        cout << a[i] << " ";
    }
    return 0;
}
